package lyl.link;

import java.util.HashMap;
import java.util.Map;

//带随机指针的链表的深拷贝
public class MyRandomLinkList {

    class Node {
        int val;
        Node next;
        Node random;

        public Node() {
        }

        public Node(int val) {
            this.val = val;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }

        public Node getRandom() {
            return random;
        }

        public void setRandom(Node random) {
            this.random = random;
        }
    }

    //用hash表存储复制的节点
    public Node doCopyRandomListMap(Node head){
        Node newHead = head; //移动原链表
        Node dummy = new Node(-1);//连接,穿起来
        Map<Node,Node> map = new HashMap<>();//新老节点的映射
        while(newHead!=null){
            Node newNode;
            if(map.containsKey(newHead)){
                newNode = map.get(newHead);
            }else {
                newNode = new Node(newHead.val);
                map.put(newHead,newNode);
            }
            dummy.next = newNode;
            if(newHead.random!=null){
                Node random = newHead.random;
                if(map.containsKey(random)){
                    newNode.random =map.get(random);
                }else {
                    Node newRandom = new Node(random.val);
                    newNode.random = newRandom;
                    map.put(random,newRandom);
                }
            }
            dummy = newNode;
            newHead = newHead.next;

        }
        return map.get(head);
    }

    //将复制的节点放在当前节点的后面
    public Node doCopyRandomList(Node head){
        if(head == null){
            return head;
        }
        //1.copy node
        Node curHead = head;
        while (curHead != null){
            Node newNode = new Node(curHead.val);
            Node next = curHead.next;
            curHead.next = newNode;
            newNode.next = next;
            curHead = next;
        }
        //2.copy random
        Node randomHead = head;
        while(randomHead != null){
            Node random = randomHead.random;
            if(random != null){
                Node newNode = randomHead.next;
                newNode.random = random.next;
            }
            randomHead = randomHead.next.next;
        }
        //split node
        Node newHead = head.next;
        Node oldHead = head;
        while(oldHead!=null){
            Node temp = oldHead.next;
            Node next = temp.next;
            oldHead.next = next;
            if(next != null){
                temp.next = next.next;
            }
            oldHead = next;
        }
        return newHead;

    }
}
